1. Field of the Invention
The present invention relates to memory management. More particularly, the present invention relates to apparatus and methods of managing a plurality of data queues stored in linked lists in a shared common memory. The invention has particular application to the use of a very large scale integrated circuit (VLSI) for the buffering of telecommunications information such as ATM data, although it is not limited thereto.
2. State of the Art
In high speed communication networks, the management of buffer resources is one mechanism of increasing network performance. One group of methods of managing buffer resources is known as sharing, where a single RAM is simultaneously utilized as a buffer by a plurality of different channels. Various sharing methods are known (see Velamuri, R. et al., "A Multi-Queue Flexible Buffer Manager Architecture", IEEE Document No. 0-7803-0917-0/93) and each has inherent advantages coupled with inherent disadvantages in terms of blocking probability, utilization, throughput, and delay. What is common to all sharing methods, however, is that a mechanism is required to direct data into appropriate locations in the RAM in a desired order so that the data can be retrieved from the RAM appropriately. One such mechanism which is well known is the use of link lists which are used to manage multiple queues sharing a common memory buffer. Typically, a link list comprises bytes of data, where each byte has at least one pointer (forward and/or backward) attached to it, thereby identifying the location of the next byte of data in the queue. The link list typically includes extensive initialization and self-check procedures which are carried out by a microprocessor on a non-real-time basis. Thus, the use of standard prior art link list structures to manage multiplex queues sharing a common memory is not readily adaptable for VLSI implementation, and is likewise not particularly suited to the handling of very high speed telecommunications information where processing and handling are dictated by the data rate of the real-time telecommunications signal.